package com.xie.leetcode.array;

//18. 四数之和
//        给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
//
//        0 <= a, b, c, d < n
//a、b、c 和 d 互不相同
//        nums[a] + nums[b] + nums[c] + nums[d] == target
//        你可以按 任意顺序 返回答案 。
//
//        示例 1：
//
//        输入：nums = [1,0,-1,0,-2,2], target = 0
//        输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
//        示例 2：
//
//        输入：nums = [2,2,2,2,2], target = 8
//        输出：[[2,2,2,2]]
//
//        提示：
//
//        1 <= nums.length <= 200
//        -10^9 <= nums[i] <= 10^9
//        -10^9 <= target <= 10^9

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author xiezhendong
 * @date 2022/3/14
 */
public class FourSum {

    public static void main(String[] args) {
        FourSum fourSum = new FourSum();
        System.out.println(fourSum.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
        System.out.println(fourSum.fourSum(new int[]{2, 2, 2, 2, 2}, 8));
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length < 4) {
            return new LinkedList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> fourSumRes = new LinkedList<>();
        for (int a = 0; a < nums.length - 3; a++) {
            if ((long) nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) {
                return fourSumRes;
            }
            if ((long) nums[a] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                continue;
            }

            if (a > 0 && nums[a] == nums[a - 1]) {
                continue;
            }
            for (int b = a + 1; b < nums.length - 2; b++) {
                if (b > a + 1 && nums[b] == nums[b - 1]) {
                    continue;
                }
                int tmp = target - nums[a] - nums[b];
                int d = nums.length - 1;
                for (int c = b + 1; c < nums.length - 1; c++) {
                    if (c > b + 1 && nums[c] == nums[c - 1]) {
                        continue;
                    }
                    while (c < d && nums[c] + nums[d] > tmp) {
                        d--;
                    }
                    if (c < d && nums[c] + nums[d] == tmp) {
                        fourSumRes.add(Arrays.asList(nums[a], nums[b], nums[c], nums[d]));
                    }
                }
            }
        }
        return fourSumRes;
    }
}
